package zuo.algo.c08;

import zuo.algo.data.graph.Edge;
import zuo.algo.data.graph.Graph;
import zuo.algo.data.graph.Node;
import zuo.algo.util.GraphUtils;

import java.util.*;

/**
 * 01:59-Dijkstra(最短路径算法)
 */
public class Dijkstra {

    static class Element {
        private int distance;
        private Node node;

        Element(int distance, Node node) {
            this.distance = distance;
            this.node = node;
        }
    }

    public static Map<Node, Integer> exc1(Node node) {
        Map<Node, Integer> res = new HashMap<>();
        res.put(node, 0);

        List<Element> distanceList = new ArrayList<>();
        distanceList.add(new Element(0, node));

        Set<Node> usedNodeSet = new HashSet<>();
        Node minNode = getMinDistanceNode(res, usedNodeSet);
        while (minNode != null) {
            usedNodeSet.add(minNode);
            Integer minDis = res.get(minNode);
            for (Edge edge : minNode.edges) {
                Integer distance = res.get(edge.to);
                int newDis = minDis + edge.weight;
                if (distance == null || distance > newDis) {
                    res.put(edge.to, newDis);
                }
            }
            minNode = getMinDistanceNode(res, usedNodeSet);
        }
        return res;
    }

    public static Node getMinDistanceNode(Map<Node, Integer> distanceMap, Set<Node> usedNodeSet) {
        int minVal = Integer.MAX_VALUE;
        Node minNode = null;
        for (Map.Entry<Node, Integer> entry : distanceMap.entrySet()) {
            if (usedNodeSet.contains(entry.getKey())) {
                continue;
            }
            if (minVal > entry.getValue()) {
                minNode = entry.getKey();
                minVal = entry.getValue();
            }
        }
        return minNode;
    }

    public static void main(String[] args) {
        int[][] matrix = {
                {0, 2, 20, 13, 0, 0, 0, 0},
                {2, 0, 4, 0, 0, 0, 0, 0},
                {20, 4, 0, 3, 100, 10, 0, 0},
                {13, 0, 3, 0, 0, 0, 0, 0},
                {0, 100, 0, 0, 0, 0, 0, 0},
                {0, 10, 0, 0, 0, 0, 9, 1},
                {0, 0, 0, 0, 0, 9, 0, 0},
                {0, 0, 0, 0, 0, 1, 0, 0},
        };
        Graph graph = GraphUtils.createGraph1(matrix);
        Map<Node, Integer> exc1 = exc1(graph.nodes.get(0));
        System.out.println();
    }
}
